import random

def visit(vp,num_of_page,algorithm):
    page_fault_times = 0
    page_list = []
    page_last_used_list = []
    nop_now = 0
    now_index = 0
    for i in range(len(vp)):
        index = 0
        page_fault_times += 1
        if nop_now < num_of_page and page_list.count(vp[i]) == 0:
            page_list.append(vp[i])
            page_last_used_list.append(i)
            nop_now += 1
        elif page_list.count(vp[i]) == 0:
            if algorithm == 0:#OPT
                max = 0
                vp_temp = vp[i:]
                for j in range(num_of_page):
                    temp = vp_temp.count(page_list[j])
                    if temp == 0:
                        index = j
                        break
                    elif vp_temp.index(page_list[j]) > max:
                        max = vp_temp.index(page_list[j])
                        index = j
            elif algorithm == 1:#FCFS
                index = now_index
                now_index += 1
                if now_index == num_of_page:
                    now_index = 0
            elif algorithm == 2:#LRU
                max = len(vp)
                for j in range(num_of_page):
                    if page_last_used_list[j] < max:
                        max = page_last_used_list[j]
                        index = j
            page_list.pop(index)
            page_list.insert(index,vp[i])
        else :
            page_last_used_list[page_list.index(vp[i])] = i
            page_fault_times -= 1
        print("访问页数：",vp[i],"页表变化为：",page_list)
    print("缺页数：",page_fault_times)
    print("缺页率：",page_fault_times/len(vp))

def main():
    num_of_page = int(input("请输入页帧数："))
    if num_of_page <= 0:
        print("请输入正整数")
        exit(0)
    num_of_vp = int(input("请输入需要调度的序列长度："))
    rand_vp = int(input("是否需要随机生成调度序列：\n1 不需要 0 需要\n"))
    vp = []
    if rand_vp == 1 :
        vp = list(map(int,input("请输入需要调度的页序列：").split()))
        print("输入的调度序列是",vp)
    else :
        for i in range(num_of_vp):
            vp.append(random.randrange(10))
        print("生成的调度序列是",vp)
    while(1):
        algorithm = int(input("请选择需要计算的算法：\n0 OPT 1 FCFS 2 LRU 3 退出\n"))
        if algorithm == 3:
            break
        print("置换过程如下：")
        visit(vp,num_of_page,algorithm)

if __name__ == '__main__':
    main()
